/**
 * @a https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
 */

#include "common.h"

class Solution
{
public:
    vector<int> countSmaller(vector<int> &nums)
    {
        int i = 0;
        for (auto num : nums)
        {
            index_nums_bind.push_back({num, i++});
        }
        ans.resize(i);
        tmp.resize(i);

        mergeSort(index_nums_bind.begin(), index_nums_bind.end());
        
        return move(ans);
    }
    void mergeSort(vector<pair<int, int>>::iterator begin, vector<pair<int, int>>::iterator end)
    {
        int sz = end - begin;
        if (sz <= 1)
            return;
        auto mid = begin + (sz >> 1);
        mergeSort(begin, mid);
        mergeSort(mid, end);

        auto cur1 = begin, cur2 = mid;
        int i = 0;
        // descending
        while (cur1 < mid && cur2 < end)
        {
            if (cur1->first <= cur2->first)
            {
                tmp[i++] = *cur2++;
            }
            else
            {
                ans[cur1->second] += end - cur2;
                tmp[i++] = *cur1++;
            }
        }
        while (cur1 < mid)
        {
            tmp[i++] = *cur1++;
        }
        while (cur2 < end)
        {
            tmp[i++] = *cur2++;
        }
        copy(tmp.begin(), tmp.begin() + sz, begin);
        return;
    }

private:
    vector<pair<int, int>> index_nums_bind;
    vector<int> ans;
    vector<pair<int, int>> tmp;
};


class Solution
{
private:
    vector<pair<int, int>> index_nums;
    vector<pair<int, int>> tmp;
    vector<int> ans;

public:
    vector<int> countSmaller(vector<int> &nums)
    {
        const int n = nums.size();
        ans.resize(n);
        tmp.resize(n);
        index_nums.reserve(n);

        for (int i = 0; i < n; ++i)
            index_nums.emplace_back(nums[i], i);

        mergeSort(index_nums.begin(), index_nums.end());
        return ans;
    }

    void mergeSort(vector<pair<int, int>>::iterator begin, vector<pair<int, int>>::iterator end)
    {
        const int sz = end - begin;
        if (sz <= 1)
            return;

        auto mid = begin + (sz >> 1); // 修正分割点
        mergeSort(begin, mid);
        mergeSort(mid, end);

        auto left = begin, right = mid;
        int i = 0;
        int right_processed = 0; // 记录已处理的右半元素数

        // 降序归并，统计右侧较小元素
        while (left < mid && right < end)
        {
            if (left->first > right->first)
            {
                ans[left->second] += (end - right); // 关键统计逻辑
                tmp[i++] = *left++;
            }
            else
            {
                tmp[i++] = *right++;
            }
        }

        // 处理剩余左半元素（不需要再统计）
        while (left < mid)
            tmp[i++] = *left++;

        // 处理剩余右半元素
        while (right < end)
            tmp[i++] = *right++;

        // 写回原数组
        copy(tmp.begin(), tmp.begin() + sz, begin);
    }
};